package org.example.myleet.p1030;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 暴力法，填满每个点之后直接计算距离排序
 * 15 ms
 * O(RC)*O(RC*ln(RC)) = O((RC)^2 * ln(RC))
 */
public class Solution {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        //填满每个点
        int[][] result = new int[R*C][2];
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                //计算偏移多少行
                int offset = i*C;
                //点的坐标
                result[offset+j][0] = i;
                result[offset+j][1] = j;
            }
        }
        //找到参照点
        int[] p0 = result[r0*C + c0];
        //直接计算曼哈顿距离排序
        Arrays.sort(result, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (Math.abs(o1[0]-p0[0]) + Math.abs(o1[1]-p0[1])) - (Math.abs(o2[0]-p0[0]) + Math.abs(o2[1]-p0[1]));
            }
        });
        return result;
    }
}
